package labuladong.binaryTree;

import com.google.common.primitives.Ints;

import java.util.List;

import static labuladong.binaryTree.BuildTree.createTree;

/**
 * @Author: David
 * @Date: 2021/4/21  10:37
 * @Version 1.0
 */
public class binary_tree_maximum_path_sum {

    public static void main(String[] args) {
        int[] rootInt = {-10,9,20,0,0,15,7};
        List<Integer> integerList = Ints.asList(rootInt);
        //创建一个树
        Node root = createTree(rootInt);

        int i = oneSideMax(root);
        System.out.println("i = " + i);
    }

    static int ans = Integer.MIN_VALUE;
    /**
     * 遍历
     * @param root
     * @return
     */
    static  int oneSideMax (Node root) {

        if (root == null) {
            return 0;
        }
        // 后序遍历
        // 直到最左边
        int left = Integer.max(0, oneSideMax(root.getLeft()));
        // 直到最右边
        int right = Integer.max(0, oneSideMax(root.getRight()));

        System.out.println("路径 => " + left +"=>"+ root.getVal() +"=>"+ right );

        ans = Integer.max(ans, left + right + root.getVal());
        return Integer.max(left, right) + root.getVal();
    }
    /**
     * LeetCode 124 题
     * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/
     * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/shou-hui-tu-jie-hen-you-ya-de-yi-dao-dfsti-by-hyj8/
     * 疑问:
     * 为什么只要算最大贡献值就可以?
     * 如果全为负的呢?
     *
     * 分析题目:
     * 路径: 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     * 路径和: 是路径中各节点值的总和。
     * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
     *
     * ① 朴实的算法
     *   1.遍历 所有的路径
     *     怎么 遍历所有的路径?
     *
     * 2.比较 所有的路径(用一个变量放最大值)
     *
     * ②
     *
     * ③ 小巧思
     *  先知条件, 后序遍历路线:
     *  遍历    最左边的   左节点->右节点->中节点
     *
     *  取最大值的思路
     *  如何遍历
     *  处理    比较
     *
     *
     * 1. 读懂这个方法的整体框架: 遍历树中的后序遍历
     *    回溯
     * 2. 处理特殊情况
     *
     */


}
